<?php
/**
 * 堆
 * 
 * 堆上的每个节点对应的数组的索引值
 * 0-   0
 * 1-   1        2
 * 2-   3   4    5     6
 * 3-   7 8 9 10 11 12 13 14
 */
class Heap
{
    public $list=[];
    /**
     * 将元素上浮
     * @return true
     */
    protected function up($index)
    {
        if($index===0){
            return true;
        }
        $sup_index= $index%2===1 ? ($index-1)/2 : $index/2-1;
        if($this->list[$sup_index] > $this->list[$index]){
            $temp=$this->list[$index];
            $this->list[$index]=$this->list[$sup_index];
            $this->list[$sup_index]=$temp;
            return $this->up($sup_index);
        }
    }
    /**
     * 将元素下浮
     * @return int
     */
    protected function down($index)
    {
        $left_index=2*$index+1;
        $right_index=$left_index+1;
        if(!isset($this->list[$left_index])){
            return $index;
        }
        elseif(!isset($this->list[$right_index])){
            $this->list[$index]=$this->list[$left_index];
            return $left_index;
        }
        elseif($this->list[$left_index] > $this->list[$right_index]){
            $this->list[$index]=$this->list[$right_index];
            return $this->down($right_index);
        }
        else{
            $this->list[$index]=$this->list[$left_index];
            return $this->down($left_index);
        }
    }
    public function insert($item)
    {
        $index=count($this->list);
        $this->list[]=$item;
        return $this->up($index);
    }
    public function popMin()
    {
        $min=$this->list[0];
        $index=$this->down(0);
        if($index===(count($this->list)-1)){
            array_pop($this->list);
        }
        else{
            $this->list[$index]=array_pop($this->list);
            $this->up($index);
        }
        return $min;
    }
    public function insertList($list)
    {
        foreach($list as $item){
            $this->insert($item);
        }
        return true;
    }
    public function popMinList()
    {
        // echo "初始状态\r\n";
        // echo $this->output()."\r\n";
        $count=count($this->list);
        $list=[];
        for($i=1;$i<=$count;$i++){
            $item=$this->popMin();
            // echo "弹出最小值:$item\r\n";
            // echo $this->output()."\r\n";
            $list[]=$item;
        }
        return $list;
    }
    protected function output_line($line,$tab,$sup_str="")
    {
        $tabs="";
        for($i=0;$i<$tab;$i++){
            $tabs.="\t";
        }
        $start=pow(2,$line)-1;
        $length=pow(2,$line);
        $str="";
        for($i=$start;$i<$start+$length;$i++){
            if(isset($this->list[$i])){
                $str.=$this->list[$i].$tabs;
            }
            else{
                return $sup_str.$str."\r\n";
            }
        }
        return $this->output_line($line+1,$tab/2,$sup_str.$str."\r\n");
    }
    public function output()
    {
        $count=count($this->list);
        $hight=ceil(log($count,2));
        $tab_num=pow(2,$hight-1);
        return $this->output_line(0,$tab_num);
    }
}




